import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class BinaryTreePaths {
    /*
    * 257. 二叉树的所有路径
    * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
    * 叶子节点 是指没有子节点的节点。
    *
    * 树中节点的数目在范围 [1, 100] 内
    * -100 <= Node.val <= 100
    * */
    public static void main(String[] args){

    }

    // 我的想法：小脑瓜不是很聪明，想不出来了
    public List<String> mySolution(TreeNode root){

        return null;
    }

    // 递归，先序遍历节点，用一个list记录路程，到了叶子节点就记录结果
    public List<String> solution(TreeNode root){
        ArrayList<String> res = new ArrayList<>();
        if (root == null)
            return res;
        LinkedList<Integer> path = new LinkedList<>();
        traversal(root, path, res);
        return res;
    }

    private void traversal(TreeNode cur, LinkedList<Integer> path, List<String> res){
        // 进入回溯栈
        path.add(cur.val);
        // 结束条件：遇到叶子节点
        if(cur.left == null && cur.right == null){
            // 生成结果
            String r = path.stream().map(i -> Integer.toString(i))
                    .collect(Collectors.joining("->"));
            res.add(r);
            return;
        }

        // 向左和右遍历
        if(cur.left != null){
            traversal(cur.left, path, res);
            // 遍历完这个节点一定记得回溯弹出，表示这个节点已经访问完了
            path.pollLast();
        }
        if(cur.right != null){
            traversal(cur.right, path, res);
            // 遍历完这个节点一定记得回溯弹出，表示这个节点已经访问完了
            path.pollLast();
        }
        return;
    }

    // 迭代法 这里要注意，记录的路径和遍历的节点放在一个栈里
    // 每遍历一个节点，都要向栈中存放到达该节点的路径
    public List<String> solution2(TreeNode root){
        ArrayList<String> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<String> path = new LinkedList<>();
        stack.add(root);
        path.add(root.val+"");
        while (!stack.isEmpty()){
            root = stack.pollLast();
            String r = path.pollLast();
            if(root.left == null && root.right == null){
                res.add(r);
                continue;
            }
            if(root.right != null){
                stack.add(root.right);
                path.add(r + "->" + root.right.val );
            }
            if(root.left != null){
                stack.add(root.left);
                path.add(r + "->" + root.left.val);
            }
        }
        return res;
    }
}
